/*
    SUSAN® - Sole of Unix Save ANything

   Copyright (C) 2005-2011 Hechzh Property

   
*/
/*
 * SUSAN red-black binary tree routines.
 *
 * rblist is a binary tree with the links being in the data item.
 *
 * Developed in part from ideas obtained from several online University courses.
 *
 * Kern Sibbald, November MMV
 */

#include "include/susan.h"
#include "lib/rblist.h"

/*
 *  Insert an item in the tree, but only if it is unique
 *   otherwise, the item is returned non inserted
 *  The big trick is keeping the tree balanced after the
 *   insert. We use a parent pointer to make it simpler and
 *   to avoid recursion.
 *
 * Returns: item         if item inserted
 *          other_item   if same value already exists (item not inserted)
 */
void* rblist::insert(void* item, int compare(void* item1, void* item2))
{
  void *x, *y;
  void* last = NULL; /* last leaf if not found */
  void* found = NULL;
  int comp = 0;

  /* Search */
  x = head;
  while (x && !found) {
    last = x;
    comp = compare(item, x);
    if (comp < 0) {
      x = left(x);
    } else if (comp > 0) {
      x = right(x);
    } else {
      found = x;
    }
  }

  if (found) {    /* found? */
    return found; /* yes, return item found */
  }
  SetLeft(item, NULL);
  SetRight(item, NULL);
  SetParent(item, NULL);
  SetRed(item, false);
  /* Handle empty tree */
  if (num_items == 0) {
    head = item;
    num_items++;
    return item;
  }
  x = last;
  /* Not found, so insert it on appropriate side of tree */
  if (comp < 0) {
    SetLeft(last, item);
  } else {
    SetRight(last, item);
  }
  SetRed(last, true);
  SetParent(item, last);
  num_items++;

  /* Now we must walk up the tree balancing it */
  x = last;
  while (x != head && red(parent(x))) {
    if (parent(x) == left(parent(parent(x)))) {
      /* Look at the right side of our grandparent */
      y = right(parent(parent(x)));
      if (y && red(y)) {
        /* our parent must be black */
        SetRed(parent(x), false);
        SetRed(y, false);
        SetRed(parent(parent(x)), true);
        x = parent(parent(x)); /* move up to grandpa */
      } else {
        if (x == right(parent(x))) { /* right side of parent? */
          x = parent(x);
          LeftRotate(x);
        }
        /* make parent black too */
        SetRed(parent(x), false);
        SetRed(parent(parent(x)), true);
        RightRotate(parent(parent(x)));
      }
    } else {
      /* Look at left side of our grandparent */
      y = left(parent(parent(x)));
      if (y && red(y)) {
        SetRed(parent(x), false);
        SetRed(y, false);
        SetRed(parent(parent(x)), true);
        x = parent(parent(x)); /* move up to grandpa */
      } else {
        if (x == left(parent(x))) {
          x = parent(x);
          RightRotate(x);
        }
        /* make parent black too */
        SetRed(parent(x), false);
        SetRed(parent(parent(x)), true);
        LeftRotate(parent(parent(x)));
      }
    }
  }
  /* Make sure the head is always black */
  SetRed(head, false);
  return item;
}

/*
 * Search for item
 */
void* rblist::search(void* item, int compare(void* item1, void* item2))
{
  void* found = NULL;
  void* x;
  int comp;

  x = head;
  while (x) {
    comp = compare(item, x);
    if (comp < 0) {
      x = left(x);
    } else if (comp > 0) {
      x = right(x);
    } else {
      found = x;
      break;
    }
  }
  return found;
}

/*
 * Get first item (i.e. lowest value)
 */
void* rblist::first(void)
{
  void* x;

  x = head;
  down = true;
  while (x) {
    if (left(x)) {
      x = left(x);
      continue;
    }
    return x;
  }
  /* Tree is empty */
  return NULL;
}

/*
 * This is a non-recursive btree walk routine that returns
 *  the items one at a time in order. I've never seen a
 *  non-recursive tree walk routine published that returns
 *  one item at a time rather than doing a callback.
 *
 * Return the next item in sorted order.  We assume first()
 *  was called once before calling this routine.
 *  We always go down as far as we can to the left, then up, and
 *  down one to the right, and again down as far as we can to the
 *  left.  etc.
 *
 * Returns: pointer to next larger item
 *          NULL when no more items in tree
 */
void* rblist::next(void* item)
{
  void* x;

  if (!item) { return first(); }

  x = item;
  if ((down && !left(x) && right(x)) || (!down && right(x))) {
    /* Move down to right one */
    down = true;
    x = right(x);
    /* Then all the way down left */
    while (left(x)) { x = left(x); }
    return x;
  }

  /* We have gone down all we can, so now go up */
  for (;;) {
    /* If at head, we are done */
    if (!parent(x)) { return NULL; }
    /* Move up in tree */
    down = false;
    /* if coming from right, continue up */
    if (right(parent(x)) == x) {
      x = parent(x);
      continue;
    }
    /* Coming from left, go up one -- ie. return parent */
    return parent(x);
  }
}

/*
 * Similer to next(), but visits all right nodes when
 *  coming up the tree.
 */
void* rblist::any(void* item)
{
  void* x;

  if (!item) { return NULL; }

  x = item;
  if ((down && !left(x) && right(x)) || (!down && right(x))) {
    /* Move down to right one */
    down = true;
    x = right(x);
    /* Then all the way down left */
    while (left(x)) { x = left(x); }
    return x;
  }

  /* We have gone down all we can, so now go up */
  for (;;) {
    /* If at head, we are done */
    if (!parent(x)) { return NULL; }
    down = false;
    /* Go up one and return parent */
    return parent(x);
  }
}


/* x is item, y is below and to right, then rotated to below left */
void rblist::LeftRotate(void* item)
{
  void* y;
  void* x;

  x = item;
  y = right(x);
  SetRight(x, left(y));
  if (left(y)) { SetParent(left(y), x); }
  SetParent(y, parent(x));
  /* if no parent then we have a new head */
  if (!parent(x)) {
    head = y;
  } else if (x == left(parent(x))) {
    SetLeft(parent(x), y);
  } else {
    SetRight(parent(x), y);
  }
  SetLeft(y, x);
  SetParent(x, y);
}

void rblist::RightRotate(void* item)
{
  void *x, *y;

  y = item;
  x = left(y);
  SetLeft(y, right(x));
  if (right(x)) { SetParent(right(x), y); }
  SetParent(x, parent(y));
  /* if no parent then we have a new head */
  if (!parent(y)) {
    head = x;
  } else if (y == left(parent(y))) {
    SetLeft(parent(y), x);
  } else {
    SetRight(parent(y), x);
  }
  SetRight(x, y);
  SetParent(y, x);
}


void rblist::remove(void* item) {}

/* Destroy the tree contents.  Not totally working */
void rblist::destroy()
{
  void *x, *y = NULL;

  x = first();
  // printf("head=%p first=%p left=%p right=%p\n", head, x, left(x), right(x));
  for (; (y = any(x));) {
    /* Prune the last item */
    if (parent(x)) {
      if (x == left(parent(x))) {
        SetLeft(parent(x), NULL);
      } else if (x == right(parent(x))) {
        SetRight(parent(x), NULL);
      }
    }
    if (!left(x) && !right(x)) {
      if (head == x) { head = NULL; }
      //          if (num_items<30) {
      //             printf("free nitems=%d item=%p left=%p right=%p\n",
      //             num_items, x, left(x), right(x));
      //          }
      free((void*)x); /* free previous node */
      num_items--;
    }
    x = y; /* save last node */
  }
  if (x) {
    if (x == head) { head = NULL; }
    //    printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x,
    //    left(x), right(x));
    free((void*)x);
    num_items--;
  }
  if (head) {
    //    printf("Free head\n");
    free((void*)head);
  }
  // printf("free nitems=%d\n", num_items);

  head = NULL;
}
